package targetToOffer.seventhDay;

/**
 * @author Godc
 * @description
 */
public class SingleNumbers {
    public static void main(String[] args) {
        SingleNumbersSolution s = new SingleNumbersSolution();
        int[] ints = s.singleNumbers(new int[]{1, 2, 5, 2});
    }
}
class SingleNumbersSolution {
    public int[] singleNumbers(int[] nums) {
        // 分组异或
        int eor = 0;
        for(int i = 0;i<nums.length;i++){
            eor^=nums[i];
        }
        // 假设两个不同数字为a，b，则eor=a^b
        // 先求出最右侧1
        int m = 1;
        while((eor&m)==0){
            m = m<<1;
        }
        // 另一种求最右侧1的方法
        eor = (~eor+1)&eor;
        int x = 0,y = 0;
        for(int i = 0;i<nums.length;i++){
            if((nums[i]&m)==0){
                // 说明不同位是0的组别
                x^=nums[i];
            }else y^=nums[i];
        }

        return new int[]{x,y};

    }
}